package com.code.answer;

import com.code.ListNode;

import java.util.*;

/**
 * leetcode 简单题
 *
 * @author Ysl
 * @create 2025/7/21 10:03
 */
public class Simple {

    public static void main(String[] args) {
//        int[] nums = {9, 9};
//        int[] nums1 = plusOne(nums);
//        for (int i = 0; i < nums1.length; i++) {
//            System.out.print(nums1[i]);
//        }

        System.out.println("qw:"+addBinary("1111", "1111"));
        System.out.println();
    }


    /**
     * 67. 二进制求和
     *
     * @param a
     * @param b
     * @return
     */
    public static String addBinary(String a, String b) {
        // TODO 不会
        return "";
    }


    /**
     * 66. 加一
     *
     * @param digits
     * @return
     */
    public static int[] plusOne(int[] digits) {
        int length = digits.length;

        for (int i = length - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i]++;
                return digits;
            } else {
                digits[i] = 0;
            }
        }

        if (digits[0] == 0) {
            int[] nums = new int[length + 1];
            nums[0] = 1;
            return nums;
        }

        return digits;
    }

    /**
     * 58. 最后一个单词的长度
     *
     * @param s
     * @return
     */
    public static int lengthOfLastWord(String s) {
        while (s.endsWith(" ")) {
            s = s.substring(0, s.length() - 1);
        }

        int count = 0;
        char[] charArray = s.toCharArray();
        for (int i = charArray.length - 1; i >= 0; i--) {
            if (charArray[i] == ' ') {
                break;
            }
            count++;
        }
        return count;
    }

    /**
     * 58. 最后一个单词的长度
     * 官方解法
     *
     * @param s
     * @return
     */
    public static int lengthOfLastWord2(String s) {
        int index = s.length() - 1;
        while (s.charAt(index) == ' ') {
            index--;
        }
        int wordLength = 0;
        while (index >= 0 && s.charAt(index) != ' ') {
            wordLength++;
            index--;
        }
        return wordLength;
    }

    /**
     * 35. 搜索插入位置
     * 二分法
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     *
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert(int[] nums, int target) {
        if (nums[0] > target) {
            return 0;
        } else if (nums[nums.length - 1] < target) {
            return nums.length;
        }

        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;

    }

    /**
     * 28. 找出字符串中第一个匹配项的下标
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack, String needle) {
        int h = haystack.length();
        int n = needle.length();

        if (h < n) {
            return -1;
        } else if (h == n && haystack.equals(needle)) {
            return 0;
        }

        int index = 0;

        int count = 0;
        for (int i = 0; i < h; i++) {
            index = i;
            while (count < n && (h - i >= n)) {

                if (haystack.charAt(index) != needle.charAt(count)) {
                    count = 0;
                    break;
                }
                count++;
                index++;
            }

            if (count == n) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 27. 移除元素
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量
     * 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要
     * 返回 k
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {

            if (nums[i] != val) {
                nums[index] = nums[i];
                index++;
            }

        }
        return index;
    }

    /**
     * 26. 删除有序数组中的重复项
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int index = 0;

        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                nums[index] = nums[i];
                index++;
            }
            if (i > 0 && nums[i] != nums[index - 1]) {
                nums[index] = nums[i];
                index++;
            }
        }
        return index;
    }

    /**
     * 21. 合并两个有序链表
     *
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.getVal() < list2.getVal()) {
            ListNode node = mergeTwoLists(list1.getNext(), list2);
            list1.setNext(node);
            return list1;
        } else {
            ListNode node = mergeTwoLists(list1, list2.getNext());
            list2.setNext(node);
            return list2;
        }
    }

    /**
     * 20. 有效的括号
     *
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        // TODO 不会栈，后进先出
        // stack.pop() 弹出
        // stack.push() 压入
        // 栈的 peek() 获取栈顶元素

        Deque<Character> stack = new LinkedList<Character>();

        return true;
    }

    /**
     * 14. 最长公共前缀
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        String str = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (!str.isEmpty() && !strs[i].startsWith(str)) {
                str = str.substring(0, str.length() - 1);
            }
        }
        return str;
    }

    /**
     * 13. 罗马数字转整数
     *
     * @param s
     * @return
     */
    public static int romanToInt(String s) {
//        字符          数值
//        I             1
//        V             5
//        X             10
//        L             50
//        C             100
//        D             500
//        M             1000
//        I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
//        X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
//        C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int result = 0;

        for (int i = 0; i < s.length(); i++) {
            if (i < s.length() - 1 && map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
                result -= map.get(s.charAt(i));
            } else {
                result += map.get(s.charAt(i));
            }
        }
        return result;
    }

    /**
     * 9. 回文数
     *
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        // 负数直接返回 false
        if (x < 0) {
            return false;
        }
        // 0 或个位数直接返回 true
        if (x < 10) {
            return true;
        }

        int original = x;
        int reversed = 0;

        // 反转数字
        while (x > 0) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }

        return original == reversed;
    }

    /**
     * 9. 回文数
     * 进阶：你能不将整数转为字符串来解决这个问题吗？
     *
     * @param x
     * @return
     */
    public static boolean isPalindrome2(int x) {
        // 负数直接返回 false
        if (x < 0) {
            return false;
        }
        // 0 或个位数直接返回 true
        if (x < 10) {
            return true;
        }

        String string = String.valueOf(x);
        int left = 0;
        int right = string.length() - 1;
        while (left < right) {
            if (string.charAt(left) != string.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /**
     * 1. 两数之和
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int tag = target - nums[i];
            if (map.containsKey(tag)) {
                return new int[]{map.get(tag), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}
